/***************************************************************/
/**                                                           **/
/**        João Marco Maciel da Silva          7577598        **/
/**        Exercício-Programa 03                              **/
/**                                                           **/
/***************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <locale.h>
#include <time.h>

/*#define MAX_BOARDSIZE 200*/
#define NPRIMOS 26

typedef unsigned int hashNum;
typedef char ** mat;
typedef struct elemento hT;

/*entrada para hashTable, contem um pointer para matrixes, para que as colisões entrem sempre no mesmo lugar*/
/*how much diz quantas matrixes há para uma determinada chave*/
struct elemento {
    char valid;
    mat matrix;
    hT *next;
};

/*abstrações das funções do programa*/
/*a descrição delas está junto ao corpo delas*/
mat initMatrix();
unsigned int pot(unsigned int power);
void tryCatch(void *pointer);
void printBoard ();
void pushMatrix();
char areEquals(mat compare);
char isSingle();
void calculateHash();
void pushBishop();
char pop();
void searchBoards();
char searchNextBoard();
char nextSafe();
void printTime(time_t* pt1, time_t* pt2);
void printResult();

/*variáveis globais, usei variáveis globais porque estas variáveis estavam sendo chamadas pela maioria das funções*/
/*size do tabuleiro e quantidade de bishops*/
unsigned char size, bishops;
/*contador de boards e boards não equivalentes*/
unsigned int boards=0, naoEquivalentes=0;
/*verifica as options i e v*/
unsigned char i=0, v=0;
/*variáveis para a busca do próximo lugar livre*/
unsigned char j=0, k=0;
/*verifica as diagonais ocupadas*/
unsigned char *BitPosDiag, *BitNegDiag;
/*conta o número de bishops presentes no tabuleiro*/
unsigned char presentes=0;
/*matrix do tabuleiro*/
mat matrix;
/*hashKey da matrix presente*/
hashNum key;
/*tabela de hash*/
hT *hashTable;
/*colisoes de hashKey*/
unsigned int colisoes=0;
/*estado de erro, para sair do programa caso não consiga alocar memória*/
char errorState = 0;
/*lista de primos para tabela de hash*/
unsigned int primos[] = {
    53,
    97,
    193,
    389,
    769,
    1543,
    3079,
    6151,
    12289,
    24593,
    49157,
    98317,
    196613,
    393241,
    786433,
    1572869,
    3145739,
    6291469,
    12582917,
    25165843,
    50331653,
    100663319,
    201326611,
    402653189,
    805306457,
    1610612741
};
/*primo escolhido*/
unsigned int p;

/*inicializa matrz em branco*/
mat initMatrix() {
    unsigned char i, j;
    mat matrix;
    matrix = (mat) malloc (size * sizeof(char*));
    for(i=0; i<size; i++) {
        matrix[i] = (char *) malloc (size * sizeof(char));
        for(j=0; j<size; j++) matrix[i][j] = 0;
    }
    return matrix;
}

/*esta função calcula a potência 2^power recusivamente e já tirando a congruência mod p, de modo mais rápido que %*/
unsigned int pot(unsigned int power) {
    unsigned int value;
    if (power == 0) return 1;
    if (power == 1) return 2;
    value = 2*pot(power-1);
    if (value >= p) return value-p;
    return value;
}

/*coloquei esta função apenas para verificar se um pointer foi devidamente alocado*/
void tryCatch(void *pointer) {
    if (pointer == NULL) {
        printf("Erro, não foi possivel alocar memória ou memória insuficiente\n");
        errorState = 1; /*talvez fosse mais usável neste caso um 'goto', mas acho feio*/
    }
}

/*imprime o tabuleiro, a ser usado a cada nova classe caso a opção "i" tenha sido passada*/
void printBoard () {
    unsigned char i, j;
    for (i=0; i<size; i++) {
        for(j=0; j<size; j++) printf(" %d", matrix[i][j]);
        printf("\n");
    }
    printf("\n");
}

/*adiciona uma matrix a hash table*/
void pushMatrix() {
    unsigned char i, j;
    hT aux;
    
    if (hashTable[key].valid == 0) {
        hashTable[key].next = (hT *)malloc(sizeof(hT));
        tryCatch(hashTable[key].next);
        if (!errorState) {
            hashTable[key].next->next = NULL;
            hashTable[key].next->matrix = initMatrix();
            for (i=0; i<size; i++)
                for (j=0; j<size; j++)
                    hashTable[key].next->matrix[i][j] = matrix[i][j];
        }
        hashTable[key].valid = 1;
    }
    else {
        aux = hashTable[key];
        while (aux.next->next != NULL) aux = *aux.next;
        aux.next->next = (hT *)malloc(sizeof(hT));
        aux = *aux.next;
        tryCatch(aux.next);
        if (!errorState) {
            aux.next->next = NULL;
            aux.next->matrix = initMatrix();
            for (i=0; i<size; i++)
                for (j=0; j<size; j++)
                    aux.next->matrix[i][j] = matrix[i][j];
        }
    }
}

/*verifica se duas matrixes são de mesma classe com rotações e espelhamentos*/
char areEquals(mat compare) {
    unsigned char i, j, l=size-1;
    char equals=1;
    /*verificam semelhança por rotações*/
    for(i=0; equals == 1 && i<size; i++)
        for(j=0; equals == 1 && j<size; j++)
            if (matrix[i][j] != compare[j][l-i]) equals = 0;
    if(equals==1) return 1;
    
    equals=1;
    for(i=0; equals == 1 && i<size; i++)
        for(j=0; equals == 1 && j<size; j++)
            if (matrix[i][j] != compare[l-i][l-j]) equals = 0;
    if(equals==1) return 1;
    
    equals=1;
    for(i=0; equals == 1 && i<size; i++)
        for(j=0; equals == 1 && j<size; j++)
            if (matrix[i][j] != compare[l-j][i]) equals = 0;
    if(equals==1) return 1;
    
    /*verificam semelhança por reflexão com eixo na diagonal principal da original e das rotacionadas*/
    equals = 1;
    for(i=0; equals == 1 && i<size; i++)
        for(j=0; equals == 1 && j<size; j++)
            if (matrix[i][j] != compare[j][i]) equals = 0;
    if(equals==1) return 1;
    
    equals = 1;
    for(i=0; equals == 1 && i<size; i++)
        for(j=0; equals == 1 && j<size; j++)
            if (matrix[i][j] != compare[l-i][j]) equals = 0;
    if(equals==1) return 1;
    
    equals = 1;
    for(i=0; equals == 1 && i<size; i++)
        for(j=0; equals == 1 && j<size; j++)
            if (matrix[i][j] != compare[l-j][l-i]) equals = 0;
    if(equals==1) return 1;
    
    equals = 1;
    for(i=0; equals == 1 && i<size; i++)
        for(j=0; equals == 1 && j<size; j++)
            if (matrix[i][j] != compare[i][l-j]) equals = 0;
    if(equals==1) return 1;
    return 0;
}

/*verifica se não existe matrix semelhante*/
char isSingle() {
    hT aux;
    if (hashTable[key].valid == 0) return 1;
    else {
        aux = hashTable[key];
        while (aux.next!=NULL) {
            if (areEquals(aux.next->matrix)) return 0;
            aux = *aux.next;
        }
    }
    colisoes++;
    return 1;
}

/*calcula o valor do hash da matrix achada*/
/*o hash aqui é calculado também usando as diagonais*/
/*isto é um hash de chave dupla*/
/*a chave não é única, mas é igual para todos os semelhantes*/
void calculateHash() {
    unsigned char i, j;
    key=0;
    for(i=0; i<size; i++)
        for(j=0; j<size; j++)
            if (matrix[i][j])
                key += pot((j+1)*(i+1)*(size-i)*(size-j));
}

/*adiciona um bispo a matrix*/
void pushBishop() {
    matrix[j][k]=1;
    BitPosDiag[j - k + size - 1] = 1;
    BitNegDiag[k + j] = 1;
    presentes++;
    k++;
}

/*retira o ultimo bispo colocado*/
char pop() {
    if (!presentes) return 0;
    
    for (;j>=0;j--) {
        for (;k>=0;k--) {
            if (k<size && j<size && matrix[j][k]) {
                BitPosDiag[j - k + size - 1] = 0;
                BitNegDiag[k + j] = 0;
                matrix[j][k]=0;
                presentes--;
                k++;
                return 1;
            }
        }
        k=size-1;
    }
    return 0;
}

/*verifica se uma dada localização é tranquila*/
char nextSafe() {
    for(;j<size;j++) {
        for (;k<size;k++){
            if(!BitPosDiag[j - k + size - 1] && !BitNegDiag[k + j])
                return 1;
        }
        k = 0;
    }
    return 0; /*retorna 0 se não tiver mais nenhum lugar seguro após iXj*/
}

/*procura próxima matrix possível, caso exista*/
char searchNextBoard() {
    
    /*vazio, aqui só fica vazio no inicio, nas outras ele tem pelo menos 1 bispo*/
    if(presentes == 0) pushBishop();
    /*(presentes == bishops), retiro 1 para fazer a prósima busca*/
    else {
        k--;
        pop();
    }
    
    while(presentes < bishops) { 
    /*enquanto não encontra o próximo ou não acaba*/
        if (nextSafe()) pushBishop();
        else if (!pop()) return 0;
    }
    return 1;
}

/*inicializa a tabela de hash*/
void initHashTable() {
    unsigned int aux, count;
    
    /*calcula primo para tabela de hash*/
    if (bishops>size) aux = pot((unsigned int) ((2*size -1 - bishops)*(size*size-1)/size - 1));
    else aux = pot((unsigned int) (bishops*(size*size-1)/size - 1));
    for (count=1;count<NPRIMOS && primos[count]<aux;count++);
    p = primos[count-1];
    printf("p: %d\n", p);
        
    hashTable = (hT *)malloc(p*sizeof(hT));
    tryCatch(hashTable);
    for (count = 0; count<p; count++)
        hashTable[count].valid = 0;
}

/*função que acha todos os boards com size dado e número de bishops dado*/
/*os vetores BitPositiveDiagonal e BitNegativeDiagonal servem para marcar as diagonais já ocupadas pelos bishops*/
void searchBoards() {
    unsigned char count;
    BitPosDiag = (unsigned char *)malloc((2*size-1)*sizeof(char));
    tryCatch(BitPosDiag);
    BitNegDiag = (unsigned char *)malloc((2*size-1)*sizeof(char));
    tryCatch(BitNegDiag);
    
    initHashTable();
    
    if (!errorState) {
        for(count=0; count< 2*size - 1; count++) {
            BitNegDiag[j] = 0;
            BitPosDiag[j] = 0;
        }
        while (searchNextBoard() && !errorState) {
            boards++;
            calculateHash();
            if (isSingle()) {
                pushMatrix();
                if (!errorState) {
                    naoEquivalentes++;
                    if(i) printBoard();
                }
            }
        }
    }
}



/*imprime o resultado final, com o numero de boards e de classes de boards*/
void printResult() {
    printf("\t%d tabuleiro%s,\t\t%d não equivalente%s\n", boards, ((boards == 1 || !boards) ? "" : "s"),
     naoEquivalentes, ((naoEquivalentes == 1 || !naoEquivalentes) ? "" : "s"));
}

/*calcula o tempo para exibir caso a opção V seja usada */
void printTime(time_t* pt1, time_t* pt2) {
    double secs;
    int hours , mins, intsecs;

    secs = difftime(*pt2, *pt1);
    intsecs = (int)secs;
    printf("Execução durou %d segundo%s.\n", intsecs, (intsecs == 1 ? "" : "s"));

    /* Imprime horas, minutos e segundos */
    hours = intsecs/3600;
    intsecs -= hours * 3600;
    mins = intsecs/60;
    intsecs -= mins * 60;
    if (hours > 0 || mins > 0) {
        printf("Igual a ");
        if (hours > 0) {
            printf("%d hora%s, ", hours, (hours == 1) ? "" : "s");
        }
        if (mins > 0) {           
            printf("%d minuto%s e ", mins, (mins == 1) ? "" : "s");
        }
        printf("%d segundo%s.\n", intsecs, (intsecs == 1 ? "" : "s"));
    }
}

int main(int argc, char **argv) {
    unsigned char count;
    time_t t1, t2;
    int aux;
    setlocale (LC_CTYPE,"pt_BR.utf8");
    if(argc < 3) printf("Erro, número de argumentos inválido\n");
    else {
        /* pega opções */
        for(count=3; count<argc; count++) {
            if (argv[count][0] == 'i') i++;
            else if (argv[count][0] == 'v') v++;
            else {
                printf("Erro, comando %s não existe e será ignorado\n", argv[count]);
                return 0;
            }
        }
        
        aux = atoi(argv[1]);
        if (aux > 255 || aux < 0) {
            printf("tamanho do tabuleiro não permitido\n");
            return 0;
        }
        size = aux;
        aux = atoi(argv[2]);
        if (aux > 255 || aux < 0) {
            printf("número de bispos não permitido\n");
            return 0;
        }
        bishops = aux;
        
        
        /*inicia contador de tempo*/
        time(&t1);
        
        matrix = initMatrix();
        
        /*faz a contagem*/
        if (size > 1 && bishops <= 2*(size)-2 && bishops>0)
            searchBoards();
        else if(size == 1 && bishops == 1) {
            boards = 1;
            naoEquivalentes = 1;
            if (i) printf(" 1\n");
        }
        else if (!bishops && i && size) { /*estou considerando o vazio como uma possivel configuração*/
            printBoard();
            boards = 1;
            naoEquivalentes = 1;
        }
        if (!errorState) {
            /*finaliza contador de tempo*/
            time(&t2);
            
            printResult();
            if(v) {
                printTime(&t1, &t2);
                printf("Tamanho da tabela de hash: %d\n", p);
                printf("Houveram %d colisões\n", colisoes);
                printf("\n");
            }
        }
    }
    return 0;
}

